note:快速幂是一个常用经典需要好好掌握的知识点。另外此题中如何处理指数为负数的情况的方法值得总结
题目描述
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
示例 1:
1 | 输入:x = 2.00000, n = 10 |
示例 2:
1 | 输入:x = 2.10000, n = 3 |
示例 3:
1 | 输入:x = 2.00000, n = -2 |
提示:
- $-100.0 < x < 100.0$
- $-2^{31} <= n <= 2^{31}-1$
- $-10^4 <= x^n <= 10^4$
方法 快速幂算法
思路
快速幂的思想在前面几道题也有所记录,其实本质它是一种二分的思想,将复杂度为$O(n)$的循环求余的方法,复杂度精简到了$O(logn)$。
根据二分推导$x^n = x^{n/2}\times x^{n/2}=(x^2)^{n/2}$,我们的指数显然存在两种情况:
- n为偶数:$x^n = (x^2)^{n//2}$(//表示整除)
- n为奇数:$x^n=x(x^2)^{n//2}$
据此,我们可以通过循环$x=x^2$操作,每次幂都会从$n$降至$n//2$,直至n变为0;
那我们可以用一个变量存储出现奇数时单独计算多出的一项$x$,从而让我们的循环可以持续进行。
判断奇数偶数的办法可以用求余,也可以用位运算$n\&1$。
此题另外一个有趣的地方在于对于负指数的处理,很简单的解决方法就是将指数转换为$(-1)(-n)$,也就可以将$x^n$转换为$x^{-1}x^{-n}$。
还有一个问题就是由于n的范围在$[-2^{31},2^{31}-1]$。所以存在当$n=-2^{31}$的时候,直接取反会溢出的情况,所以最好将n转换为long long型参与计算。
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(logn)$。快速幂的二分思想,让我们的时间复杂度变为$logN$
- 空间复杂度$O(1)$。
原文链接: https://zijian.wang/2021/06/07/16 数值的整数次方/
版权声明: 转载请注明出处.